#include <iostream>
using namespace std;

class KMP {
public:
    int subStr(const string& text, const string& pattern) {
        int n = text.length();
        int m = pattern.length();
        if (m == 0)
            return 0;
        int matchTable[m];
        matchTable[0] = 0;

        // step1: 构建部分匹配值表
        int i = 1, j = 0;
        while (i < m) {
            if (pattern[j] == pattern[i])
                // 匹配，则更新部分匹配值表
                matchTable[i++] = ++j;
            else {
                if (j == 0)
                    // j == 0: j位于开头，不匹配则后移i
                    matchTable[i++] = 0;
                else
                    // j > 0: j不位于开头，j应当回到上一个匹配的位置
                    j = matchTable[j - 1];
            } 
        }
        // step2: 匹配pattern和text
        i = j = 0;
        while (i < n && j < m) {
            if (pattern[j] == text[i]) {
                i++;
                j++;
            }
            else {
                if (j == 0)
                    i++;
                else {
                    j = matchTable[j - 1];
                }
            }
        }
        if (j == m)
            return i - m;
        return -1;
    }
};